Best Time to Buy and Sell Stock

Question

Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one.

Example:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Analyzation

Brute Force

Simply calculate each pair that there is profit and find the largest one. This requires two loops.

The Code

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

Time & Space Complexity

• Time Complexity: Since we search n(n-1) / 2 times so it is O(n^2).
• Space Complexity: Since we only use constant number of variables, the Space Complexity is O(1).

Optimization

Find The Minimum Price

In fact, we only need to find the minimum price and increase the profit till it reaches the max price, then that is the max profit.

class Solution {
    public int maxProfit(int[] prices) {
        int mp = 0;
        
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]){
                mp += prices[i] - prices[i - 1];
            }
        }

        return mp;
    }
}

Time & Space Complexity

• Time Complexity: Since we create only one loop so it is O(n).
• Space Complexity: Since we only use constant number of variables, the Space Complexity is O(1).